home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / The World of Computer Software.iso / srcuc.zip / REGEX.C < prev    next >
C/C++ Source or Header  |  1992-04-02  |  32KB  |  1,158 lines
  1. /* -*-C-*-
  2.  
  3. $Header: /scheme/src/microcode/RCS/regex.c,v 1.11 1992/04/02 11:23:05 cph Exp $
  4.  
  5. Copyright (c) 1987-92 Massachusetts Institute of Technology
  6.  
  7. This material was developed by the Scheme project at the Massachusetts
  8. Institute of Technology, Department of Electrical Engineering and
  9. Computer Science.  Permission to copy this software, to redistribute
  10. it, and to use it for any purpose is granted, subject to the following
  11. restrictions and understandings.
  12.  
  13. 1. Any copy made of this software must include this copyright notice
  14. in full.
  15.  
  16. 2. Users of this software agree to make their best efforts (a) to
  17. return to the MIT Scheme project any improvements or extensions that
  18. they make, so that these may be included in future releases; and (b)
  19. to inform MIT of noteworthy uses of this software.
  20.  
  21. 3. All materials developed as a consequence of the use of this
  22. software shall duly acknowledge such use, in accordance with the usual
  23. standards of acknowledging credit in academic research.
  24.  
  25. 4. MIT has made no warrantee or representation that the operation of
  26. this software will be error-free, and MIT is under no obligation to
  27. provide any services, by way of maintenance, update, or otherwise.
  28.  
  29. 5. In conjunction with products arising from the use of this material,
  30. there shall be no use of the name of the Massachusetts Institute of
  31. Technology nor of any adaptation thereof in any advertising,
  32. promotional, or sales literature without prior written consent from
  33. MIT in each case. */
  34.  
  35. /* Regular expression matching and search. */
  36.  
  37. /* NOTE: This program was created by translation from the regular
  38. expression code of GNU Emacs; it was translated from the original C to
  39. 68000 assembly language (in 1986), and then translated back from 68000
  40. assembly language to C (in 1987).  Users should be aware that the GNU
  41. GENERAL PUBLIC LICENSE may apply to this code.  A copy of that license
  42. should have been included along with this file. */
  43.  
  44. #include "scheme.h"
  45. #include "syntax.h"
  46. #include "regex.h"
  47.  
  48. extern char * malloc ();
  49. extern char * realloc ();
  50. extern void free ();
  51.  
  52. #ifndef SIGN_EXTEND_CHAR
  53. #define SIGN_EXTEND_CHAR(x) (x)
  54. #endif /* not SIGN_EXTEND_CHAR */
  55.  
  56. #ifndef SWITCH_ENUM
  57. #define SWITCH_ENUM(enum_type, expression)                \
  58.   switch ((enum enum_type) (expression))
  59. #endif /* not SWITCH_ENUM */
  60.  
  61. #ifndef RE_NFAILURES
  62. #define RE_NFAILURES 512
  63. #endif
  64.  
  65. #define FOR_INDEX_RANGE(index, start, end)                \
  66.   for (index = (start); (index < (end)); index += 1)
  67.  
  68. #define FOR_INDEX_BELOW(index, limit)                    \
  69.   FOR_INDEX_RANGE (index, 0, (limit))
  70.  
  71. #define FOR_ALL_ASCII(index)                        \
  72.   FOR_INDEX_BELOW (index, MAX_ASCII)
  73.  
  74. #define FOR_ALL_ASCII_SUCH_THAT(index, expression)            \
  75.   FOR_ALL_ASCII (index)                            \
  76.     if (expression)
  77.  
  78. #define TRANSLATE_CHAR(ascii)                        \
  79.   ((translation == NULL) ? (ascii) : (translation [(ascii)]))
  80.  
  81. #define WORD_CONSTITUENT_P(ascii)                    \
  82.   (SYNTAX_CONSTITUENT_P (syntaxcode_word, (ascii)))
  83.  
  84. #define SYNTAX_CONSTITUENT_P(code, ascii)                \
  85.   ((SYNTAX_ENTRY_CODE (SYNTAX_TABLE_REF (syntax_table, (ascii)))) == (code))
  86.  
  87. #define CHAR_SET_MEMBER_P(length, char_set, ascii)            \
  88.   (((ascii) < ((length) * ASCII_LENGTH)) &&                \
  89.    (CHAR_SET_MEMBER_P_INTERNAL (char_set, ascii)))
  90.  
  91. #define CHAR_SET_MEMBER_P_INTERNAL(char_set, ascii)            \
  92.   ((((char_set) [((ascii) / ASCII_LENGTH)]) &                \
  93.     (1 << ((ascii) % ASCII_LENGTH)))                    \
  94.    != 0)
  95.  
  96. #define READ_PATTERN_CHAR(target) do                    \
  97. {                                    \
  98.   if (pattern_pc >= pattern_end)                    \
  99.     BAD_PATTERN ();                            \
  100.   (target) = (*pattern_pc++);                        \
  101. } while (0)
  102.  
  103. #define READ_PATTERN_OFFSET(target) do                    \
  104. {                                    \
  105.   if ((pattern_pc + 1) >= pattern_end)                    \
  106.     BAD_PATTERN ();                            \
  107.   (target) = (*pattern_pc++);                        \
  108.   (target) +=                                \
  109.     ((SIGN_EXTEND_CHAR (* ((char *) (pattern_pc++)))) << ASCII_LENGTH);    \
  110.   if (((pattern_pc + (target)) < pattern_start) ||            \
  111.       ((pattern_pc + (target)) > pattern_end))                \
  112.     BAD_PATTERN ();                            \
  113. } while (0)
  114.  
  115. #define READ_PATTERN_LENGTH(target) do                    \
  116. {                                    \
  117.   if ((pattern_pc >= pattern_end) ||                    \
  118.       ((pattern_pc + ((target) = (*pattern_pc++))) > pattern_end))    \
  119.     BAD_PATTERN ();                            \
  120. } while (0)
  121.  
  122. #define READ_PATTERN_REGISTER(target) do                \
  123. {                                    \
  124.   if ((pattern_pc >= pattern_end) ||                    \
  125.       (((target) = (*pattern_pc++)) >= RE_NREGS))            \
  126.     BAD_PATTERN ();                            \
  127. } while (0)
  128.  
  129. #define READ_PATTERN_SYNTAXCODE(target) do                \
  130. {                                    \
  131.   if ((pattern_pc >= pattern_end) ||                    \
  132.       (((int) ((target) = ((enum syntaxcode) (*pattern_pc++))))        \
  133.        >= ((int) syntaxcode_max)))                    \
  134.     BAD_PATTERN ();                            \
  135. } while (0)
  136.  
  137. #define BAD_PATTERN() RE_RETURN (-2)
  138.  
  139. #define PUSH_FAILURE_POINT(pattern_pc, match_pc) do            \
  140. {                                    \
  141.   if (stack_pointer == stack_end)                    \
  142.     {                                    \
  143.       long stack_length;                        \
  144.       unsigned char **stack_temporary;                    \
  145.                                     \
  146.       stack_length = ((stack_end - stack_start) * 2);            \
  147.       if (stack_length > (re_max_failures * 2))                \
  148.     RE_RETURN (-4);                            \
  149.       stack_temporary =                            \
  150.     ((unsigned char **)                        \
  151.      (realloc                            \
  152.       (stack_start, (stack_length * (sizeof (unsigned char *))))));    \
  153.       if (stack_temporary == NULL)                    \
  154.     RE_RETURN (-3);                            \
  155.       stack_end = (& (stack_temporary [stack_length]));            \
  156.       stack_pointer =                            \
  157.     (& (stack_temporary [(stack_pointer - stack_start)]));        \
  158.       stack_start = stack_temporary;                    \
  159.     }                                    \
  160.   (*stack_pointer++) = (pattern_pc);                    \
  161.   (*stack_pointer++) = (match_pc);                    \
  162. } while (0)
  163.  
  164. #define RE_RETURN(value)                        \
  165. {                                    \
  166.   return_value = (value);                        \
  167.   goto return_point;                            \
  168. }
  169.  
  170. void
  171. DEFUN (re_buffer_initialize,
  172.        (buffer, translation, syntax_table, text,
  173.     text_start_index, text_end_index,
  174.     gap_start_index, gap_end_index),
  175.        struct re_buffer * buffer
  176.        AND unsigned char * translation
  177.        AND SYNTAX_TABLE_TYPE syntax_table
  178.        AND unsigned char * text
  179.        AND unsigned long text_start_index
  180.        AND unsigned long text_end_index
  181.        AND unsigned long gap_start_index
  182.        AND unsigned long gap_end_index)
  183. {
  184.   unsigned char *text_start, *text_end, *gap_start, *gap_end;
  185.  
  186.   /* Assumes that
  187.      ((text_start_index <= gap_start_index) &&
  188.       (gap_start_index <= gap_end_index) &&
  189.       (gap_end_index <= text_end_index)) */
  190.  
  191.   text_start = (text + text_start_index);
  192.   text_end = (text + text_end_index);
  193.   gap_start = (text + gap_start_index);
  194.   gap_end = (text + gap_end_index);
  195.  
  196.   (buffer -> translation) = translation;
  197.   (buffer -> syntax_table) = syntax_table;
  198.   (buffer -> text) = text;
  199.   (buffer -> text_start) = ((text_start == gap_start) ? gap_end : text_start);
  200.   (buffer -> text_end) = ((text_end == gap_end) ? gap_start : text_end);
  201.   (buffer -> gap_start) = gap_start;
  202.   (buffer -> gap_end) = gap_end;
  203.   return;
  204. }
  205.  
  206. /* Given a compiled pattern between `pattern_start' and `pattern_end',
  207.    generate a character set which is true of all characters which can
  208.    be the first character of a match.
  209.  
  210.    See the documentation of `struct re_buffer' for a description of
  211.    `translation' and `syntax_table'.
  212.  
  213.    `fastmap' is the resulting character set.  It is a character array
  214.    whose elements are either `FASTMAP_FALSE' or `FASTMAP_TRUE'.
  215.  
  216.    Return values:
  217.    0 => pattern cannot match the null string.
  218.    1 => pattern can match the null string.
  219.    2 => pattern can match the null string, but only at end of match
  220.      text or to left of a character in `fastmap'.
  221.    -2 => the pattern is improperly formed.
  222.    else => undefined. */
  223.  
  224. #define FASTMAP_FALSE '\0'
  225. #define FASTMAP_TRUE '\1'
  226.  
  227. int
  228. DEFUN (re_compile_fastmap,
  229.        (pattern_start, pattern_end, translation, syntax_table, fastmap),
  230.        unsigned char * pattern_start
  231.        AND fast unsigned char * pattern_end
  232.        AND unsigned char * translation
  233.        AND SYNTAX_TABLE_TYPE syntax_table
  234.        AND fast unsigned char * fastmap)
  235. {
  236.   fast unsigned char *pattern_pc;
  237.   unsigned char *stack_start[RE_NFAILURES];
  238.   unsigned char **stack_pointer;
  239.   int return_value;
  240.  
  241.   pattern_pc = pattern_start;
  242.   return_value = 0;
  243.   stack_pointer = stack_start;
  244.  
  245.   {
  246.     fast int i;
  247.  
  248.     FOR_ALL_ASCII (i)
  249.       (fastmap [i]) = FASTMAP_FALSE;
  250.   }
  251.  
  252.  loop:
  253.   if (pattern_pc >= pattern_end)
  254.     RE_RETURN (1);
  255.  
  256.   SWITCH_ENUM (regexpcode, (*pattern_pc++))
  257.     {
  258.     case regexpcode_unused:
  259.     case regexpcode_line_start:
  260.     case regexpcode_buffer_start:
  261.     case regexpcode_buffer_end:
  262.     case regexpcode_word_start:
  263.     case regexpcode_word_end:
  264.     case regexpcode_word_bound:
  265.     case regexpcode_not_word_bound:
  266.       goto loop;
  267.  
  268.     case regexpcode_line_end:
  269.       {
  270.     (fastmap [(TRANSLATE_CHAR ('\n'))]) = FASTMAP_TRUE;
  271.     if (return_value == 0)
  272.       return_value = 2;
  273.     goto next;
  274.       }
  275.  
  276.     case regexpcode_exact_1:
  277.       {
  278.     fast int ascii;
  279.  
  280.     READ_PATTERN_CHAR (ascii);
  281.     (fastmap [(TRANSLATE_CHAR (ascii))]) = FASTMAP_TRUE;
  282.     goto next;
  283.       }
  284.  
  285.     case regexpcode_exact_n:
  286.       {
  287.     fast int length;
  288.  
  289.     READ_PATTERN_LENGTH (length);
  290.     if (length == 0)
  291.       goto loop;
  292.     (fastmap [(TRANSLATE_CHAR (pattern_pc [0]))]) = FASTMAP_TRUE;
  293.     goto next;
  294.       }
  295.  
  296.     case regexpcode_any_char:
  297.       {
  298.     fast int ascii;
  299.  
  300.     FOR_ALL_ASCII_SUCH_THAT (ascii, (ascii != '\n'))
  301.       (fastmap [(TRANSLATE_CHAR (ascii))]) = FASTMAP_TRUE;
  302.     if (return_value != 0)
  303.       goto return_point;
  304.     goto next;
  305.       }
  306.  
  307.     case regexpcode_char_set:
  308.       {
  309.     fast int length;
  310.     fast int ascii;
  311.  
  312.     READ_PATTERN_LENGTH (length);
  313.     length = (length * ASCII_LENGTH);
  314.     FOR_INDEX_BELOW (ascii, length)
  315.       if (CHAR_SET_MEMBER_P_INTERNAL (pattern_pc, ascii))
  316.         (fastmap [(TRANSLATE_CHAR (ascii))]) = FASTMAP_TRUE;
  317.     goto next;
  318.       }
  319.  
  320.     case regexpcode_not_char_set:
  321.       {
  322.     fast int length;
  323.     fast int ascii;
  324.  
  325.     READ_PATTERN_LENGTH (length);
  326.     length = (length * ASCII_LENGTH);
  327.     FOR_INDEX_BELOW (ascii, length)
  328.       if (! (CHAR_SET_MEMBER_P_INTERNAL (pattern_pc, ascii)))
  329.         (fastmap [(TRANSLATE_CHAR (ascii))]) = FASTMAP_TRUE;
  330.     FOR_INDEX_RANGE (ascii, length, MAX_ASCII)
  331.       (fastmap [(TRANSLATE_CHAR (ascii))]) = FASTMAP_TRUE;
  332.     goto next;
  333.       }
  334.  
  335.     case regexpcode_word_char:
  336.       {
  337.     fast int ascii;
  338.  
  339.     FOR_ALL_ASCII_SUCH_THAT (ascii, (WORD_CONSTITUENT_P (ascii)))
  340.       (fastmap [(TRANSLATE_CHAR (ascii))]) = FASTMAP_TRUE;
  341.     goto next;
  342.       }
  343.  
  344.     case regexpcode_not_word_char:
  345.       {
  346.     fast int ascii;
  347.  
  348.     FOR_ALL_ASCII_SUCH_THAT (ascii, (! (WORD_CONSTITUENT_P (ascii))))
  349.       (fastmap [(TRANSLATE_CHAR (ascii))]) = FASTMAP_TRUE;
  350.     goto next;
  351.       }
  352.  
  353.     case regexpcode_syntax_spec:
  354.       {
  355.     fast enum syntaxcode code;
  356.     fast int ascii;
  357.  
  358.     READ_PATTERN_SYNTAXCODE (code);
  359.     FOR_ALL_ASCII_SUCH_THAT (ascii, (SYNTAX_CONSTITUENT_P (code, ascii)))
  360.       (fastmap [(TRANSLATE_CHAR (ascii))]) = FASTMAP_TRUE;
  361.     goto next;
  362.       }
  363.  
  364.     case regexpcode_not_syntax_spec:
  365.       {
  366.     fast enum syntaxcode code;
  367.     fast int ascii;
  368.  
  369.     READ_PATTERN_SYNTAXCODE (code);
  370.     FOR_ALL_ASCII_SUCH_THAT (ascii,
  371.                  (! (SYNTAX_CONSTITUENT_P (code, ascii))))
  372.       (fastmap [(TRANSLATE_CHAR (ascii))]) = FASTMAP_TRUE;
  373.     goto next;
  374.       }
  375.  
  376.     case regexpcode_start_memory:
  377.     case regexpcode_stop_memory:
  378.       {
  379.     fast int register_number;
  380.  
  381.     READ_PATTERN_REGISTER (register_number);
  382.     goto loop;
  383.       }
  384.  
  385.     case regexpcode_duplicate:
  386.       {
  387.     fast int register_number;
  388.     fast int ascii;
  389.  
  390.     READ_PATTERN_REGISTER (register_number);
  391.     FOR_ALL_ASCII (ascii)
  392.       (fastmap [ascii]) = FASTMAP_TRUE;
  393.     RE_RETURN (1);
  394.       }
  395.  
  396.     case regexpcode_jump:
  397.     case regexpcode_finalize_jump:
  398.     case regexpcode_maybe_finalize_jump:
  399.     case regexpcode_dummy_failure_jump:
  400.       {
  401.     fast int offset;
  402.  
  403.     return_value = 1;
  404.     READ_PATTERN_OFFSET (offset);
  405.     pattern_pc += offset;
  406.     if (offset > 0)
  407.       goto loop;
  408.  
  409.     /* Jump backward reached implies we just went through the
  410.        body of a loop and matched nothing.  Opcode jumped to
  411.        should be an on_failure_jump.  Just treat it like an
  412.        ordinary jump.  For a * loop, it has pushed its failure
  413.        point already; if so, discard that as redundant. */
  414.     if (pattern_pc >= pattern_end)
  415.       BAD_PATTERN ();
  416.     if (((enum regexpcode) (pattern_pc [0])) !=
  417.         regexpcode_on_failure_jump)
  418.       goto loop;
  419.     READ_PATTERN_OFFSET (offset);
  420.     pattern_pc += offset;
  421.     if ((stack_pointer != stack_start) &&
  422.         ((stack_pointer [-1]) == pattern_pc))
  423.       stack_pointer -= 1;
  424.     goto loop;
  425.       }
  426.  
  427.     case regexpcode_on_failure_jump:
  428.       {
  429.     fast int offset;
  430.  
  431.     READ_PATTERN_OFFSET (offset);
  432.     (*stack_pointer++) = (pattern_pc + offset);
  433.     goto loop;
  434.       }
  435.  
  436.     default:
  437.       BAD_PATTERN ();
  438.     }
  439.  
  440.  next:
  441.   if (stack_pointer != stack_start)
  442.     {
  443.       pattern_pc = (*--stack_pointer);
  444.       goto loop;
  445.     }
  446.  
  447.  return_point:
  448.   return (return_value);
  449. }
  450.  
  451. /* Match the compiled pattern described by `pattern_start' and
  452.    `pattern_end' against the characters in `buffer' between
  453.    `match_start' and `match_end'.
  454.  
  455.    `registers', if not NULL, will be filled with the start and end
  456.    indices of the match registers if the match succeeds.
  457.  
  458.    It is assumed that the following is true:
  459.  
  460.    (! ((gap_start < gap_end) &&
  461.        (match_start < match_end) &&
  462.        ((match_start == gap_start) || (match_end == gap_end))))
  463.  
  464.    Return values:
  465.  
  466.    non-negative => the end index (exclusive) of the match.
  467.    -1 => no match.
  468.    -2 => the pattern is badly formed.
  469.    -3 => memory allocation error.
  470.    -4 => match stack overflow.
  471.    other => undefined. */
  472.  
  473. #define RE_MATCH_FAILED (-1)
  474.  
  475. #define ADDRESS_TO_INDEX(address)                    \
  476.   ((((address) > gap_start) ? ((address) - gap_length) : (address))    \
  477.    - (buffer -> text))
  478.  
  479. #define READ_MATCH_CHAR(target) do                    \
  480. {                                    \
  481.   if (match_pc >= match_end)                        \
  482.     goto re_match_fail;                            \
  483.   (target) = (TRANSLATE_CHAR (*match_pc++));                \
  484.   if (match_pc == gap_start)                        \
  485.     match_pc = gap_end;                            \
  486. } while (0)
  487.  
  488. static Boolean
  489. beq_translate (scan1, scan2, length, translation)
  490.      fast unsigned char *scan1, *scan2;
  491.      fast long length;
  492.      fast unsigned char *translation;
  493. {
  494.   while ((length--) > 0)
  495.     if ((TRANSLATE_CHAR (*scan1++)) != (TRANSLATE_CHAR (*scan2++)))
  496.       return (false);
  497.   return (true);
  498. }
  499.  
  500. int re_max_failures = 1000;
  501.  
  502. int
  503. DEFUN (re_match,
  504.        (pattern_start, pattern_end, buffer, registers, match_start, match_end),
  505.        unsigned char * pattern_start
  506.        AND unsigned char * pattern_end
  507.        AND struct re_buffer * buffer
  508.        AND struct re_registers * registers
  509.        AND unsigned char * match_start
  510.        AND unsigned char * match_end)
  511. {
  512.   fast unsigned char *pattern_pc, *match_pc;
  513.   unsigned char *gap_start, *gap_end;
  514.   unsigned char *translation;
  515.   SYNTAX_TABLE_TYPE syntax_table;
  516.   long gap_length;
  517.   int return_value;
  518.  
  519.   /* Failure point stack.  Each place that can handle a failure
  520.      further down the line pushes a failure point on this stack.  It
  521.      consists of two char *'s.  The first one pushed is where to
  522.      resume scanning the pattern; the second pushed is where to resume
  523.      scanning the match text.  If the latter is NULL, the failure
  524.      point is a "dummy".  If a failure happens and the innermost
  525.      failure point is dormant, it discards that failure point and
  526.      tries the next one. */
  527.  
  528.   unsigned char **stack_start, **stack_end, **stack_pointer;
  529.  
  530.   /* Information on the "contents" of registers.  These are pointers
  531.      into the match text; they record just what was matched (on this
  532.      attempt) by some part of the pattern.  The start_memory command
  533.      stores the start of a register's contents and the stop_memory
  534.      command stores the end.
  535.  
  536.      At that point, (register_start [regnum]) points to the first
  537.      character in the register, and (register_end [regnum]) points to
  538.      the first character beyond the end of the register. */
  539.  
  540.   unsigned char *register_start[RE_NREGS];
  541.   unsigned char *register_end[RE_NREGS];
  542.  
  543.   pattern_pc = pattern_start;
  544.   match_pc = match_start;
  545.   gap_start = (buffer -> gap_start);
  546.   gap_end = (buffer -> gap_end);
  547.   gap_length = (gap_end - gap_start);
  548.   translation = (buffer -> translation);
  549.   syntax_table = (buffer -> syntax_table);
  550.  
  551.   stack_start =
  552.     ((unsigned char **) (malloc ((2 * RE_NFAILURES) * (sizeof (char *)))));
  553.   if (stack_start == NULL)
  554.     RE_RETURN (-3);
  555.  
  556.   stack_end = (& (stack_start [(2 * RE_NFAILURES)]));
  557.   stack_pointer = stack_start;
  558.  
  559.   {
  560.     fast int i;
  561.  
  562.     FOR_INDEX_BELOW (i, RE_NREGS)
  563.       {
  564.     (register_start [i]) = NULL;
  565.     (register_end [i]) = NULL;
  566.       }
  567.   }
  568.  
  569.  re_match_loop:
  570.   if (pattern_pc >= pattern_end)
  571.     {
  572.       /* Reaching here indicates that match was successful. */
  573.       if (registers != NULL)
  574.     {
  575.       fast int i;
  576.  
  577.       (register_start [0]) = match_start;
  578.       (register_end [0]) = match_pc;
  579.       FOR_INDEX_BELOW (i, RE_NREGS)
  580.         {
  581.           ((registers -> start) [i]) =
  582.         (((register_start [i]) == NULL)
  583.          ? -1
  584.          : (ADDRESS_TO_INDEX (register_start [i])));
  585.           ((registers -> end) [i]) =
  586.         (((register_end [i]) == NULL)
  587.          ? -1
  588.          : (ADDRESS_TO_INDEX (register_end [i])));
  589.         }
  590.     }
  591.       RE_RETURN (ADDRESS_TO_INDEX (match_pc));
  592.     }
  593.  
  594.   SWITCH_ENUM (regexpcode, (*pattern_pc++))
  595.     {
  596.     case regexpcode_unused:
  597.       goto re_match_loop;
  598.  
  599.     case regexpcode_exact_1:
  600.       {
  601.     fast int ascii;
  602.     fast int ascii_p;
  603.  
  604.     READ_MATCH_CHAR (ascii);
  605.     READ_PATTERN_CHAR (ascii_p);
  606.     if (ascii == ascii_p)
  607.       goto re_match_loop;
  608.     goto re_match_fail;
  609.       }
  610.  
  611.     case regexpcode_exact_n:
  612.       {
  613.     fast int length;
  614.     fast int ascii;
  615.  
  616.     READ_PATTERN_LENGTH (length);
  617.     while ((length--) > 0)
  618.       {
  619.         READ_MATCH_CHAR (ascii);
  620.         if (ascii != (*pattern_pc++))
  621.           goto re_match_fail;
  622.       }
  623.     goto re_match_loop;
  624.       }
  625.  
  626.     case regexpcode_any_char:
  627.       {
  628.     fast int ascii;
  629.  
  630.     READ_MATCH_CHAR (ascii);
  631.     if (ascii == '\n')
  632.       goto re_match_fail;
  633.     goto re_match_loop;
  634.       }
  635.  
  636. #define RE_MATCH_CHAR_SET(winning_label, losing_label)            \
  637.       {                                    \
  638.     fast int ascii;                            \
  639.     fast int length;                        \
  640.                                     \
  641.     READ_MATCH_CHAR (ascii);                    \
  642.     READ_PATTERN_LENGTH (length);                    \
  643.     if (CHAR_SET_MEMBER_P (length, pattern_pc, ascii))        \
  644.       {                                \
  645.         pattern_pc += length;                    \
  646.         goto winning_label;                        \
  647.       }                                \
  648.     else                                \
  649.       {                                \
  650.         pattern_pc += length;                    \
  651.         goto losing_label;                        \
  652.       }                                \
  653.       }
  654.  
  655.     case regexpcode_char_set:
  656.       RE_MATCH_CHAR_SET (re_match_loop, re_match_fail);
  657.  
  658.     case regexpcode_not_char_set:
  659.       RE_MATCH_CHAR_SET (re_match_fail, re_match_loop);
  660.  
  661. #undef RE_MATCH_CHAR_SET
  662.  
  663.     /* \( is represented by a start_memory, \) by a stop_memory.  Both
  664.        of those commands contain a "register number" argument.  The
  665.        text matched within the \( and \) is recorded under that
  666.        number.  Then, \<digit> turns into a `duplicate' command which
  667.        is followed by the numeric value of <digit> as the register
  668.        number. */
  669.  
  670.     case regexpcode_start_memory:
  671.       {
  672.     fast int register_number;
  673.  
  674.     READ_PATTERN_REGISTER (register_number);
  675.     (register_start [register_number]) = match_pc;
  676.     goto re_match_loop;
  677.       }
  678.  
  679.     case regexpcode_stop_memory:
  680.       {
  681.     fast int register_number;
  682.  
  683.     READ_PATTERN_REGISTER (register_number);
  684.     (register_end [register_number]) =
  685.       ((match_pc == gap_end) ? gap_start : match_pc);
  686.     goto re_match_loop;
  687.       }
  688.  
  689.     case regexpcode_duplicate:
  690.       {
  691.     fast int register_number;
  692.     unsigned char *start, *end, *new_end;
  693.     long length;
  694.  
  695.     READ_PATTERN_REGISTER (register_number);
  696.     start = (register_start [register_number]);
  697.     end = (register_end [register_number]);
  698.     length = (end - start);
  699.     if (length <= 0)
  700.       goto re_match_loop;
  701.     new_end = (match_pc + length);
  702.     if (new_end > match_end)
  703.       goto re_match_fail;
  704.     if ((match_pc <= gap_start) && (new_end > gap_start))
  705.       {
  706.         long length1, length2;
  707.  
  708.         new_end += gap_length;
  709.         if (new_end > match_end)
  710.           goto re_match_fail;
  711.         length1 = (gap_start - match_pc);
  712.         length2 = (length - length1);
  713.         if (!
  714.         ((beq_translate (match_pc, start, length1, translation)) &&
  715.          (beq_translate (gap_end, (start + length1), length2,
  716.                  translation))))
  717.           goto re_match_fail;
  718.       }
  719.     else if ((start <= gap_start) && (end > gap_start))
  720.       {
  721.         long length1, length2;
  722.  
  723.         length1 = (gap_start - start);
  724.         length2 = (end - gap_end);
  725.         if (!
  726.         ((beq_translate (match_pc, start, length1, translation)) &&
  727.          (beq_translate ((match_pc + length1), gap_end, length2,
  728.                  translation))))
  729.           goto re_match_fail;
  730.       }
  731.     else
  732.       {
  733.         if (! (beq_translate (match_pc, start, length, translation)))
  734.           goto re_match_fail;
  735.       }
  736.     match_pc = ((new_end == gap_start) ? gap_end : new_end);
  737.     goto re_match_loop;
  738.       }
  739.  
  740.     case regexpcode_buffer_start:
  741.       {
  742.     if (match_pc == (buffer -> text_start))
  743.       goto re_match_loop;
  744.     goto re_match_fail;
  745.       }
  746.  
  747.     case regexpcode_buffer_end:
  748.       {
  749.     if (match_pc == (buffer -> text_end))
  750.       goto re_match_loop;
  751.     goto re_match_fail;
  752.       }
  753.  
  754.     case regexpcode_line_start:
  755.       {
  756.     if (match_pc == (buffer -> text_start))
  757.       goto re_match_loop;
  758.     if ((TRANSLATE_CHAR
  759.          (((match_pc == gap_end) ? gap_start : match_pc) [-1]))
  760.         == '\n')
  761.       goto re_match_loop;
  762.     goto re_match_fail;
  763.       }
  764.  
  765.     case regexpcode_line_end:
  766.       {
  767.     if ((match_pc == (buffer -> text_end)) ||
  768.         ((TRANSLATE_CHAR (match_pc [0])) == '\n'))
  769.       goto re_match_loop;
  770.     goto re_match_fail;
  771.       }
  772.  
  773. #define RE_MATCH_WORD_BOUND(word_bound_p)                \
  774.   if ((match_pc == gap_end)                        \
  775.       ? (word_bound_p (((gap_start != (buffer -> text_start)) &&    \
  776.             (WORD_CONSTITUENT_P (TRANSLATE_CHAR (gap_start [-1])) \
  777.              )),                        \
  778.                ((gap_end != (buffer -> text_end)) &&        \
  779.             (WORD_CONSTITUENT_P (TRANSLATE_CHAR (gap_end [0]))) \
  780.             )))                        \
  781.       : (word_bound_p (((match_pc != (buffer -> text_start)) &&        \
  782.             (WORD_CONSTITUENT_P (TRANSLATE_CHAR (match_pc [-1]))) \
  783.             ),                        \
  784.                ((match_pc != (buffer -> text_end)) &&        \
  785.             (WORD_CONSTITUENT_P (TRANSLATE_CHAR (match_pc [0]))) \
  786.             ))))                        \
  787.       goto re_match_loop;                        \
  788.     goto re_match_fail
  789.  
  790.     case regexpcode_word_bound:
  791. #define WORD_BOUND_P(left_p, right_p) ((left_p) != (right_p))
  792.       RE_MATCH_WORD_BOUND (WORD_BOUND_P);
  793. #undef WORD_BOUND_P
  794.  
  795.     case regexpcode_not_word_bound:
  796. #define NOT_WORD_BOUND_P(left_p, right_p) ((left_p) == (right_p))
  797.       RE_MATCH_WORD_BOUND (NOT_WORD_BOUND_P);
  798. #undef NOT_WORD_BOUND_P
  799.  
  800.     case regexpcode_word_start:
  801. #define WORD_START_P(left_p, right_p) ((! (left_p)) && (right_p))
  802.       RE_MATCH_WORD_BOUND (WORD_START_P);
  803. #undef WORD_START_P
  804.  
  805.     case regexpcode_word_end:
  806. #define WORD_END_P(left_p, right_p) ((left_p) && (! (right_p)))
  807.       RE_MATCH_WORD_BOUND (WORD_END_P);
  808. #undef WORD_END_P
  809.  
  810. #undef RE_MATCH_WORD_BOUND
  811.  
  812.     case regexpcode_syntax_spec:
  813.       {
  814.     fast int ascii;
  815.     fast enum syntaxcode code;
  816.  
  817.     READ_MATCH_CHAR (ascii);
  818.     READ_PATTERN_SYNTAXCODE (code);
  819.     if (SYNTAX_CONSTITUENT_P (code, ascii))
  820.       goto re_match_loop;
  821.     goto re_match_fail;
  822.       }
  823.  
  824.     case regexpcode_not_syntax_spec:
  825.       {
  826.     fast int ascii;
  827.     fast enum syntaxcode code;
  828.  
  829.     READ_MATCH_CHAR (ascii);
  830.     READ_PATTERN_SYNTAXCODE (code);
  831.     if (! (SYNTAX_CONSTITUENT_P (code, ascii)))
  832.       goto re_match_loop;
  833.     goto re_match_fail;
  834.       }
  835.  
  836.     case regexpcode_word_char:
  837.       {
  838.     fast int ascii;
  839.  
  840.     READ_MATCH_CHAR (ascii);
  841.     if (WORD_CONSTITUENT_P (ascii))
  842.       goto re_match_loop;
  843.     goto re_match_fail;
  844.       }
  845.  
  846.     case regexpcode_not_word_char:
  847.       {
  848.     fast int ascii;
  849.  
  850.     READ_MATCH_CHAR (ascii);
  851.     if (! (WORD_CONSTITUENT_P (ascii)))
  852.       goto re_match_loop;
  853.     goto re_match_fail;
  854.       }
  855.  
  856.     /* "or" constructs ("|") are handled by starting each alternative
  857.        with an on_failure_jump that points to the start of the next
  858.        alternative.  Each alternative except the last ends with a jump
  859.        to the joining point.  (Actually, each jump except for the last
  860.        one really jumps to the following jump, because tensioning the
  861.        jumps is a hassle.)
  862.  
  863.        The start of a stupid repeat has an on_failure_jump that points
  864.        past the end of the repeat text.  This makes a failure point so
  865.        that, on failure to match a repetition, matching restarts past
  866.        as many repetitions have been found with no way to fail and
  867.        look for another one.
  868.  
  869.        A smart repeat is similar but loops back to the on_failure_jump
  870.        so that each repetition makes another failure point. */
  871.  
  872.     case regexpcode_on_failure_jump:
  873.       {
  874.     fast long offset;
  875.  
  876.     READ_PATTERN_OFFSET (offset);
  877.     PUSH_FAILURE_POINT ((pattern_pc + offset), match_pc);
  878.     goto re_match_loop;
  879.       }
  880.  
  881.     /* The end of a smart repeat has a maybe_finalize_jump back.
  882.        Change it either to a finalize_jump or an ordinary jump. */
  883.  
  884.     case regexpcode_maybe_finalize_jump:
  885.       {
  886.     fast long offset;
  887.     fast long ascii;
  888.  
  889.     READ_PATTERN_OFFSET (offset);
  890.     if (pattern_pc == pattern_end)
  891.       goto finalize_jump;
  892.  
  893.     /* Compare what follows with the beginning of the repeat.
  894.        If we can establish that there is nothing that they
  895.        would both match, we can change to `finalize_jump'. */
  896.  
  897.     SWITCH_ENUM (regexpcode, (pattern_pc [0]))
  898.       {
  899.       case regexpcode_exact_1:
  900.         ascii = (pattern_pc [1]);
  901.         break;
  902.  
  903.       case regexpcode_exact_n:
  904.         ascii = (pattern_pc [2]);
  905.         break;
  906.  
  907.       case regexpcode_line_end:
  908.         ascii = ('\n');
  909.         break;
  910.  
  911.       default:
  912.         goto dont_finalize_jump;
  913.       }
  914.  
  915.     /* (pattern_pc [(offset - 3)]) is an `on_failure_jump'.
  916.        Examine what follows that. */
  917.     SWITCH_ENUM (regexpcode, (pattern_pc [offset]))
  918.       {
  919.       case regexpcode_exact_1:
  920.         {
  921.           if (ascii != (pattern_pc [(offset + 1)]))
  922.         goto finalize_jump;
  923.           goto dont_finalize_jump;
  924.         }
  925.  
  926.       case regexpcode_exact_n:
  927.         {
  928.           if (ascii != (pattern_pc [(offset + 2)]))
  929.         goto finalize_jump;
  930.           goto dont_finalize_jump;
  931.         }
  932.  
  933.       case regexpcode_char_set:
  934.         {
  935.           if (CHAR_SET_MEMBER_P ((pattern_pc [(offset + 1)]),
  936.                      (& (pattern_pc [(offset + 2)])),
  937.                      ascii))
  938.         goto dont_finalize_jump;
  939.           goto finalize_jump;
  940.         }
  941.  
  942.       case regexpcode_not_char_set:
  943.         {
  944.           if (CHAR_SET_MEMBER_P ((pattern_pc [(offset + 1)]),
  945.                      (& (pattern_pc [(offset + 2)])),
  946.                      ascii))
  947.         goto finalize_jump;
  948.           goto dont_finalize_jump;
  949.         }
  950.  
  951.       default:
  952.         goto dont_finalize_jump;
  953.       }
  954.  
  955.       finalize_jump:
  956.     pattern_pc -= 2;
  957.     (pattern_pc [-1]) = ((unsigned char) regexpcode_finalize_jump);
  958.     goto re_match_finalize_jump;
  959.  
  960.       dont_finalize_jump:
  961.     pattern_pc -= 2;
  962.     (pattern_pc [-1]) = ((unsigned char) regexpcode_jump);
  963.     goto re_match_jump;
  964.       }
  965.  
  966.     case regexpcode_finalize_jump:
  967.     re_match_finalize_jump:
  968.       {
  969.     stack_pointer -= 2;
  970.     goto re_match_jump;
  971.       }
  972.  
  973.     case regexpcode_jump:
  974.     re_match_jump:
  975.       {
  976.     fast long offset;
  977.  
  978.     READ_PATTERN_OFFSET (offset);
  979.     pattern_pc += offset;
  980.     goto re_match_loop;
  981.       }
  982.  
  983.     case regexpcode_dummy_failure_jump:
  984.       {
  985.     PUSH_FAILURE_POINT (NULL, NULL);
  986.     goto re_match_jump;
  987.       }
  988.  
  989.     default:
  990.       {
  991.     BAD_PATTERN ();
  992.       }
  993.     }
  994.  
  995.  re_match_fail:
  996.   if (stack_pointer == stack_start)
  997.     RE_RETURN (RE_MATCH_FAILED);
  998.   match_pc = (*--stack_pointer);
  999.   pattern_pc = (*--stack_pointer);
  1000.   if (pattern_pc != NULL)
  1001.     goto re_match_loop;
  1002.   goto re_match_fail;
  1003.  
  1004.  return_point:
  1005.   if (stack_start != NULL)
  1006.     free (stack_start);
  1007.   return (return_value);
  1008. }
  1009.  
  1010. #define DEFINE_RE_SEARCH(name)                        \
  1011. int                                    \
  1012. DEFUN (name,                                \
  1013.        (pattern_start, pattern_end, buffer, registers,            \
  1014.     match_start, match_end),                    \
  1015.        unsigned char * pattern_start                    \
  1016.        AND unsigned char * pattern_end                    \
  1017.        AND struct re_buffer * buffer                    \
  1018.        AND struct re_registers * registers                \
  1019.        AND unsigned char * match_start                    \
  1020.        AND unsigned char * match_end)
  1021.  
  1022. #define INITIALIZE_RE_SEARCH(pc, limit, gap_limit)            \
  1023.   int can_be_null;                            \
  1024.   unsigned char *translation;                        \
  1025.   int match_result;                            \
  1026.                                     \
  1027.   fast unsigned char *match_pc;                        \
  1028.   fast unsigned char *match_limit;                    \
  1029.   fast unsigned char *gap_limit;                    \
  1030.   fast unsigned char *fastmap;                        \
  1031.   unsigned char fastmap_array[MAX_ASCII];                \
  1032.                                     \
  1033.   fastmap = &fastmap_array[0];                        \
  1034.   translation = (buffer -> translation);                \
  1035.   can_be_null =                                \
  1036.     (re_compile_fastmap                            \
  1037.      (pattern_start, pattern_end, translation,                \
  1038.       (buffer -> syntax_table), fastmap));                \
  1039.   if (can_be_null < 0)                            \
  1040.     return (can_be_null);                        \
  1041.                                     \
  1042.   match_pc = (pc);                            \
  1043.   match_limit = (limit);                        \
  1044.   gap_limit = (buffer -> gap_limit)
  1045.  
  1046. #define RE_SEARCH_TEST(start)                        \
  1047.   (re_match                                \
  1048.    (pattern_start, pattern_end, buffer, registers, (start), match_end))
  1049.  
  1050. #define RE_SEARCH_FORWARD_FAST(limit) do                \
  1051. {                                    \
  1052.   while (true)                                \
  1053.     {                                    \
  1054.       if (match_pc >= (limit))                        \
  1055.     break;                                \
  1056.                                     \
  1057.       if ((fastmap [(TRANSLATE_CHAR (*match_pc++))]) == FASTMAP_FALSE)    \
  1058.     continue;                            \
  1059.                                     \
  1060.       match_result = (RE_SEARCH_TEST (match_pc - 1));            \
  1061.       if (match_result == RE_MATCH_FAILED)                \
  1062.     continue;                            \
  1063.                                     \
  1064.       return (match_result);                        \
  1065.     }                                    \
  1066. } while (0)
  1067.  
  1068. DEFINE_RE_SEARCH (re_search_forward)
  1069. {
  1070.   INITIALIZE_RE_SEARCH (match_start, match_end, gap_start);
  1071.  
  1072.   if (can_be_null != 1)
  1073.     {
  1074.       if ((match_pc < gap_start) && (gap_start < match_limit))
  1075.     RE_SEARCH_FORWARD_FAST (gap_start);
  1076.       if (match_pc == gap_start)
  1077.     match_pc = (buffer -> gap_end);
  1078.       RE_SEARCH_FORWARD_FAST (match_limit);
  1079.       return
  1080.     ((can_be_null == 0)
  1081.      ? RE_MATCH_FAILED
  1082.      : (RE_SEARCH_TEST (match_limit)));
  1083.     }
  1084.   else
  1085.     {
  1086.       while (true)
  1087.     {
  1088.       match_result = (RE_SEARCH_TEST (match_pc));
  1089.       if (match_result != RE_MATCH_FAILED)
  1090.         return (match_result);
  1091.       match_pc += 1;
  1092.       if (match_pc == gap_start)
  1093.         match_pc = (buffer -> gap_end);
  1094.       if (match_pc > match_limit)
  1095.         return (RE_MATCH_FAILED);
  1096.     }
  1097.     }
  1098. }
  1099.  
  1100. #define RE_SEARCH_BACKWARD_FAST(limit) do                \
  1101. {                                    \
  1102.   while (true)                                \
  1103.     {                                    \
  1104.       if (match_pc <= (limit))                        \
  1105.     break;                                \
  1106.                                     \
  1107.       if ((fastmap [(TRANSLATE_CHAR (*--match_pc))]) == FASTMAP_FALSE)    \
  1108.     continue;                            \
  1109.                                     \
  1110.       match_result = (RE_SEARCH_TEST (match_pc));            \
  1111.       if (match_result == RE_MATCH_FAILED)                \
  1112.     continue;                            \
  1113.                                     \
  1114.       RE_SEARCH_BACKWARD_RETURN (match_pc);                \
  1115.     }                                    \
  1116. } while (0)
  1117.  
  1118. #define RE_SEARCH_BACKWARD_RETURN(start)                \
  1119.   return                                \
  1120.     ((match_result < 0)                            \
  1121.      ? match_result                            \
  1122.      : ((((start) > (buffer -> gap_start))                \
  1123.      ? ((start) - (gap_end - (buffer -> gap_start)))        \
  1124.      : (start))                            \
  1125.     - (buffer -> text)))
  1126.  
  1127. DEFINE_RE_SEARCH (re_search_backward)
  1128. {
  1129.   INITIALIZE_RE_SEARCH (match_end, match_start, gap_end);
  1130.  
  1131.   if (can_be_null != 1)
  1132.     {
  1133.       if ((match_pc > gap_end) && (gap_end > match_limit))
  1134.     RE_SEARCH_BACKWARD_FAST (gap_end);
  1135.       if (match_pc == gap_end)
  1136.     match_pc = (buffer -> gap_start);
  1137.       RE_SEARCH_BACKWARD_FAST (match_limit);
  1138.       if (can_be_null == 0)
  1139.     return (RE_MATCH_FAILED);
  1140.       match_result = (RE_SEARCH_TEST (match_limit));
  1141.       RE_SEARCH_BACKWARD_RETURN (match_limit);
  1142.     }
  1143.   else
  1144.     {
  1145.       while (true)
  1146.     {
  1147.       match_result = (RE_SEARCH_TEST (match_pc));
  1148.       if (match_result != RE_MATCH_FAILED)
  1149.         RE_SEARCH_BACKWARD_RETURN (match_pc);
  1150.       if (match_pc == gap_end)
  1151.         match_pc = (buffer -> gap_start);
  1152.       match_pc -= 1;
  1153.       if (match_pc < match_limit)
  1154.         return (RE_MATCH_FAILED);
  1155.     }
  1156.     }
  1157. }
  1158.